Search for: All records

Nonmonetary mechanisms for repeated allocation and decision making are gaining widespread use in many real-world settings. Our aim in this work is to study the performance and incentive properties of simple mechanisms based on artificial currencies in such settings. To this end, we make the following contributions: For a general allocation setting, we provide two black-box approaches to convert any one-shot monetary mechanism to a dynamic nonmonetary mechanism using an artificial currency that simultaneously guarantees vanishing gains from nontruthful reporting over time and vanishing losses in performance. The two mechanisms trade off between their applicability and their computational and informational requirements. Furthermore, for settings with two agents, we show that a particular artificial currency mechanism also results in a vanishing price of anarchy. 

Non-monetary mechanisms for repeated resource allocation are gaining widespread use in many real-world settings. Our aim in this work is to study the allocative efficiency and incentive properties of simple repeated mechanisms based on artificial currencies. Within this framework, we make three main contributions: We provide a general black-box technique to convert any static monetary mechanism to a dynamic mechanism with artificial currency, that simultaneously guarantees vanishing loss in efficiency, and vanishing gains from non-truthful bidding over time. On a computational front, we show how such a mechanism can be implemented using only sample-access to the agents' type distributions, and requires roughly twice the amount of computation as needed to run the monetary mechanism alone. For settings with two agents, we show that a particular artificial currency mechanism also results in a vanishing price of anarchy. This provides additional justification for the use of artificial currency mechanisms in practice. Moreover, we show how to leverage this result to demonstrate the existence of a Bayesian incentive-compatible mechanism with vanishing efficiency loss in this setting. Our work takes a significant step towards bridging the gap between monetary and non-monetary mechanisms, and also points to several open problems.